package dynamic;

/**题目：最长递增子序列
 * y: 1 8 2 6 4 5
 *    最长返回4： 1 2 4 5
 * @Author Gavin
 * @date 2022.01.09 21:14
 */
public class solution_9 {
    /**
     * 解题思路：
     * 1 8 2 6 4 5
     * 推断状态方程：
     *     序列           递增序列集合              最长递增序列
     *      1                   1                       1
     *     1 8                 1  8                     2
     *    1 8 2             1  8/1 2                    2
     *   ...
     *   首先比较1，此时最大递增序列长度为1，记录下来，然后8和1进行比较，8>1，此时8的递增序列
     *   长度为2，记录下来，然后比较2，2大于1，小于8，递增序列有1 2和 2两个，取最大值为2，记录
     *   2的最长为2，然后比较6，和分别和1，8，2，6比较得到最大的递增序列3，同理比较剩下的序列。
     *
     *
     */
    //Time:O(n^2) Space:O(n)
    public int solution_1(int[] nums){
        if(nums==null||nums.length==0)return 0;
        int n=nums.length,max=1;
        //保存状态的数组，存某个下标值对应的最长子序列
        int[] d=new int[n];
        d[0]=1;
        for (int i = 1; i <n ; i++) {
            for (int j = 0; j < i; j++) {
                int cur=nums[i]>nums[j]?d[j]+1:1;
                d[i]=Math.max(d[i],cur);
            }
            max=Math.max(max,d[i]);
        }
        return max;
    }
    /**
     * 上面的做法就是把每个序列都保存下来，然后取最大的序列，我们可以进行优化，优化点就是只需要保存
     * 子序列末尾数最小的那个序列就行了。比如有两个序列1 2 和1 8 那么我们只需要保存1 2就行
     */
    //Time:O(n*log(n)) Space:O(n)
    public static int solution_2(int[] nums){
        if(nums==null||nums.length==0)return 0;
        int n=nums.length,len=0;
        int[] d=new int[n];
        for(int x:nums){
            int i=binarySearch(d,len,x);
            d[i]=x;
            //如果插入的位置在最后一位的后面，长度就加1
            if(i==len)++len;
        }
        return len;
    }
    //使用二分法进行查找数字要插入的位置
    public static int binarySearch(int[] d,int len,int x){
        int low=0,high=len-1;
        while (low<=high){
            int mid=low+(high-low)/2;
            if(x<d[mid]) high=mid-1;
            else if(x>d[mid])low=mid+1;
            else return mid;
        }
        System.out.println(low+" :--: "+high);
        return low;
    }

    public static void main(String[] args) {
        int[] a={4,3,2,1};
        System.out.println(solution_2(a));
    }
}
